package org.example.algorithm.array;

import java.util.*;

/**
 * 从一个给定数组中找出k个数字的组合，和为M
 * //todo 三进制
 */

public class KSumMSolution {

    public static void main(String[] args) {
        int[] array = {1,2,3,4,5,6,8,10};
        int k = 2;
        int m = 18;
        List<List<Integer>> result = kSumM(array, 0, k, m);
        System.out.println(result);
    }

    public static List<List<Integer>> kSumM(int[] array, int index, int k, int m) {
        List<List<Integer>> result = new ArrayList<>();
        if (k == 1) {
            for (int i=index;i<array.length;i++) {
                if (array[i] == m) {
                    List<Integer> list = new ArrayList<>();
                    list.add(array[i]);
                    result.add(list);
                }
            }
            return result;
        }
        for (int i=index;i<array.length;i++) {
            List<List<Integer>> partList = kSumM(array,i+1, k-1, m-array[i]);
            if (!partList.isEmpty()) {
                for (List<Integer> sublist: partList) {
                    sublist.add(array[i]);
                    result.add(sublist);
                }
            }
        }
        return result;
    }
}